package _动态规划;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/*
 第一步：明确DP数组的含义
 第二步：明确递推公式
 第三步：DP数组初始化
 第四步：遍历顺序  (子序列，子串问题)

 */
public class dp {
    // 70：爬楼梯：https://leetcode.cn/problems/climbing-stairs/
    public int climbStairs(int n) {
        // dp[n] 表示爬到n阶有多少种方法
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    // 不同路径 https://leetcode.cn/problems/unique-paths/
    // 从dp[0]就开始存数据，因为 必须 要初始化第一行第一列
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1; // 初始化第一行和第一列
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }


    // 63 不同路径II
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
//        第一步：明确DP数组的定义是什么:到达(i,j)有dp[i][j]条路径
//        第二步：明确递推公式 dp[i][j]=dp[i-1]
//        第三步：DP数组初始化
//        第四步：遍历顺序
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];

        for (int i = 0; i < m && obstacleGrid[i][0] != 1; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n && obstacleGrid[0][j] != 1; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] != 1)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }


    public int maxProfit(int[] prices) {
        if (prices.length <= 1) {
            return 0;
        }
        //  双指针动态规划
        //  min: 股票的最低价
        //  max：获取的最大利润
        int min = prices[0], max = 0;
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(min, prices[i]);
            max = Math.max(max, prices[i] - min);
        }
        return max;
    }

    // 983：最低票价
    public int mincostTickets(int[] days, int[] costs) {
        // dp[i]表示前 i 天的总花费  1 2 3
        int dp_length = days[days.length - 1] + 1;
        int[] dp = new int[dp_length];
        // 用来记录这一天是否旅行
        HashSet<Integer> set = new HashSet<>();
        for (int day : days) {
            set.add(day);
        }
        for (int i = 1; i < dp_length; i++) {
            if (!set.contains(i))
                // 等于前一天的费用
                dp[i] = dp[i - 1];
            else
                dp[i] = Math.min(dp[Math.max(i - 1, 0)] + costs[0],
                        Math.min(dp[Math.max(i - 7, 0)] + costs[1], dp[Math.max(i - 30, 0)] + costs[2]));
        }
        return dp[dp_length - 1];
    }

    // 139：单词拆分：https://leetcode.cn/problems/word-break/
    public boolean wordBreak(String s, List<String> wordDict) {
        // todo
        return true;
    }

    // 118：杨辉三角
    public List<List<Integer>> generate(int num) {
        // 把这个杨辉三角写出来你就知道怎么递归了
        List<List<Integer>> dp = new ArrayList<>();
        for (int i = 0; i < num; i++) {
            ArrayList<Integer> row = new ArrayList<>();
            row.add(1);
            // 当前这一行   1 2 1
            for (int j = 1; j < i; j++) {
                row.add(dp.get(i - 1).get(j - 1) + dp.get(i - 1).get(j));
            }
            if (i != 0)
                row.add(1);
        }
        return dp;
    }

    public List<Integer> getRow(int rowIndex) {
        List<Integer> dp = new ArrayList<>();
        dp.add(1);
        for (int i = 1; i <= rowIndex; i++) {
            //  我们复用了一个dp，所以当前位置j的更新会对j+1产生影响
            for (int j = i - 1; j >= 1; j--) {
                dp.set(j, dp.get(j) + dp.get(j - 1)); // 更新当前行的值
            }
            dp.add(1);
        }
        return dp;
    }

    // 2221:数组的三角和
    public int triangularSum(int[] nums) {
        int count = nums.length;
        while (count > 1) {
            for (int i = 0; i < count - 1; i++) {
                nums[i] = (nums[i] + nums[i + 1]) % 10;
            }
            count--;
        }
        return nums[0];
    }

    // 198：打家劫舍：https://leetcode.cn/problems/house-robber/
    public int rob(int[] nums) {
        // 定义dp[i]表示前i天一共能偷到的最大金额
        int p0 = 0;
        int p1 = 0;
        for (int num : nums) {
            int p2 = Math.max(p0 + num, p1);
            p0 = p1;
            p1 = p2;
        }
        return p1;
    }

    // 213:打家劫舍 II :成环 （对边界进行特殊处理即可）
    // https://leetcode.cn/problems/house-robber-ii/description/
    public int robII(int[] nums) {
        if (nums.length == 1) return nums[0];
        return Math.max(rob(Arrays.copyOfRange(nums, 0, nums.length - 1)),
                rob(Arrays.copyOfRange(nums, 1, nums.length)));
    }

    // 337: 打家劫舍 III：https://leetcode.cn/problems/house-robber-iii/description/
    public int rob(TreeNode root) {
        int[] dp = dfs(root);
        return Math.max(dp[0], dp[1]);
    }

    // 后续遍历，利用递归函数来帮助我们存每一层的返回值，从叶子节点向上（后序）
    // dp[0],dp[1]分别表示对于当前节点 偷或者 不偷所对应的金额
    // 递归函数返回值，递归终止条件，单层递归逻辑
    private int[] dfs(TreeNode root) {
        if (root == null) return new int[]{0, 0};
        int[] l = dfs(root.left);
        int[] r = dfs(root.right);
        // 偷当前节点,一定不能偷它的左右孩子节点
        int v1 = root.val + r[1] + l[1];
        // 不偷当前节点，左右孩子节点可能偷, 取最大值
        // v2 = r[1] + l[1]; 这是错的，不一定非要偷，比如 4——1——2——3
        int v2 = Math.max(r[0], r[1]) + Math.max(l[0], l[1]);
        return new int[]{v1, v2};
    }

    // 300：最长递增子序列：https://leetcode.cn/problems/longest-increasing-subsequence/
    public int lengthOfLIS(int[] nums) {
        // todo
        return 0;
    }
}

















